package LimitedTimeGame.Day_0212;

/**
 * @author zxc
 * @date 2023/02/12 19:56
 **/

import java.util.Arrays;

/**
 * 题目 ：绝对差值和
 * 题目详述 ：
 * 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
 * 数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
 * 你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
 * 在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
 * |x| 定义为：
 * 如果 x >= 0 ，值为 x ，或者
 * 如果 x <= 0 ，值为 -x
 *
 * 提示：
 * n == nums1.length
 * n == nums2.length
 * 1 <= n <= 105
 * 1 <= nums1[i], nums2[i] <= 105
 *
 */
public class MinAbsoluteSumDiff {
    /**
     * 思路 ：
     * ===>
     * （1）即，遍历nums1数组中每个元素 &&
     * @param nums1
     * @param nums2
     * @return
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int len = nums1.length;
        long result = 0;
        int[] dp = nums1.clone();
        Arrays.sort(dp);
        int max = 0;

        for(int i = 0 ; i < len ; i++){
            if(nums1[i] == nums2[i]){
                continue;
            }
            int difference = Math.abs(nums1[i] - nums2[i]);
            result += difference;
            // 使用二分查找，在nums1数组的副本dp数组中，查找到与nums2[i]绝对差值最大的值;
            int left = 0;
            int right = len - 1;
            while(left < right){
                int middle = (left + right) / 2;
                // 若是dp[middle]对应元素值 <= difference的话，则使得左指针移动到 middle;
                // ===> 即，dp[middle]对应元素值可能会等于difference,所以选择使得 left = middle + 1;
                if(dp[middle] <= difference){
                    left = middle;
                }
                // 若是dp[middle]对应的元素值 > difference的话，则使得右指针移动到 middle - 1;
                // ===》 即，dp[middle]对应元素值必然是小于difference，所以选择直接使得right = middle - 1;
                else {
                    right = middle - 1;
                }
            }
            System.out.println("left : " + left + ",right : " + right);
            int temp = Math.abs(dp[right] - nums2[i]);
            if(right + 1 < len){
                temp = Math.min(temp , Math.abs(dp[right + 1] - nums2[i]));
            }
            if(temp < difference){
                max = Math.max(max , difference - temp);
            }
        }
        return (int)(result - max) % 1000000007;
    }

}
